package zuochengyun.chapter5;

import java.util.Stack;
import java.util.concurrent.atomic.AtomicInteger;

import Tree.TreeNode;

//括号字符串的有效性和最长有效长度
public class LongestValidParentheses {

	public static void main(String[] args) {
		LongestValidParentheses object = new LongestValidParentheses();
		String string = "(()())";
		System.out.println(object.longestValid(string));
	}
	
	
	public boolean isValid(String str){
		if(str == null || str.length() <= 0){
			return false;
		}
		//没有用栈，而是用一个变量来记录 ( 的数量
		int status = 0;
		int length = str.length();
		for (int i = 0; i < length; i++) {
			//如果包含其他字符，直接返回
			if(str.charAt(i) != '(' && str.charAt(i) != ')'){
				return false;
			}
			if(str.charAt(i) == ')' && --status < 0){
				return false;
			}
			if(str.charAt(i) == '('){
				status++;
			}
		}
		//最后还要判断status是否为0
		return status == 0;
	}
	
	public int longestValid(String str){
		if(str == null || str.length() <= 1){
			return 0;
		}
		int length = str.length();
		char[] chas = str.toCharArray();
		//dp[i]表示str[0 ... i] 以i结尾的当前最长有效括号长度
		int[] dp = new int[length];
		// dp[i] = 0 (if str[i] == '(')
		// dp[i] = dp[i - 2] + 2 (if str[i] == ')' && str[i - 1] == '(')
		//这个转移方程写错了,比如  () ( ()() )
		// dp[i] = dp[i - 1] + 2 (if str[i] == ')' && str[i - 1 - dp[i - 1]] == '(')
		// dp[i] = dp[i - 1] + 2 + dp[pre - 1] (pre = i - 1 - dp[i - 1] && pre > 0)
		// dp[i] = 0
		dp[1] = (chas[1] == ')' && chas[0] == '(') ? 2 : 0;
		int res = Math.max(0, dp[1]);
		for(int i = 2; i < length; i++){
			if(chas[i] == '('){
				dp[i] = 0;
			}else{
				if(chas[i - 1] == '('){
					dp[i] = dp[i - 2] + 2;
				}else if(dp[i - 1] < i && chas[i - 1 - dp[i - 1]] == '('){
					//注意我们必须判断dp[i - 1] < i
					//比如(()))
					//最后一个下标是4, dp[i - 1] = 4,如果不判断就会导致4 - 1 - 4 < 0
					int pre = i - 1 - dp[i - 1];
					//注意优先级!!!  注意优先级!!!  注意优先级!!!
					dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
				}
			}
			res = Math.max(res, dp[i]);
		}
		return res;
	}
}
